package com.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author yuelinbo
 * @date 2021/3/20 15:22:30
 **/
public class TestTree {

    public static void main(String[] args) {
        //构建三叉树
        TreeNode root = buildTree();

        List<Integer> list1 = new ArrayList<>();
        preIterator(root, list1);
        list1.forEach(System.out::println);
        System.out.println("--------开始镜像反转--------");
        //镜像反转
        invertTreeNode(root);
        List<Integer> list2 = new ArrayList<>();
        preIterator(root, list2);
        list2.forEach(System.out::println);
    }

    /**
     * 三叉树镜像反转
     */
    private static void invertTreeNode(TreeNode root) {
        if (null == root) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (stack.size() > 0) {
            TreeNode tmp = stack.lastElement();
            stack.pop();
            TreeNode tmpLeft = tmp.getLeft();
            tmp.setLeft(tmp.getRight());
            tmp.setRight(tmpLeft);

            if (null != tmp.getLeft()) {
                stack.push(tmp.getLeft());
            }

            if (null != tmp.getRight()) {
                stack.push(tmp.getRight());
            }
        }
    }

    /**
     * 构建三叉树
     *
     * @return TreeNode
     */
    public static TreeNode buildTree() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
//        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);

        //构建左节点
        node3.setLeft(node1);
        node1.setLeft(node8);
        node1.setMiddle(node2);
        node1.setRight(node7);
        node2.setLeft(node5);

        //构建右节点
        node3.setRight(node9);
        node9.setRight(node6);

        return node3;
    }

    //遍历
    public static void preIterator(TreeNode root, List<Integer> list) {
        if (root != null) {
            list.add(root.getData());
            preIterator(root.getLeft(), list);
            preIterator(root.getMiddle(), list);
            preIterator(root.getRight(), list);
        }
    }

}
